CRC (Cyclic Redundancy Check) code is used in various fields such as wireless packet communication or recording discs such as optical discs. For example, in a wireless communication system, errors are likely to occur in transmission data in a radio channel because communication is carried out through a radio link, and so an error correction circuit using CRC code is provided. CRC bits are generated based on a transmission data sequence at the transmitting end and are added to the tail of the transmission data sequence. The bit sequence to which the CRC bits are added is encoded using a coding scheme such as convolution coding or turbo coding, and the resulting encoded bit sequence is transmitted.
Non-Patent Document 1 discloses the principle of CRC code in detail.
FIG. 1 illustrates how CRC code is used.
In FIG. 1, input data sequence A from input source 11 is subjected to CRC coding in CRC coding section 12 and is transmitted as transmission data sequence B to the receiving end through channel 13. Channel 13 is, for example, a radio channel, and bit error E (i.e. noise) is added to the transmission data sequence B. The receiving end receives transmission data sequence B′ to which bit error E is added, carries out a CRC check in CRC check section 14 and gives received data A′ based on the CRC check to the outputting end 15 (i.e. sink). Here, Assume that a wireless communication system employs HARQ (Hybrid Auto Repeat reQuest) combining turbo coding with high error correction capability and ARQ (Auto Repeat reQuest). Then when CRC check section 14 carries out a CRC check and detects an error occurring situation, and, if no error occurs, CRC check section 14 outputs received data A′ of data sequence A and forms an ACK signal as an ACK/NACK signal to be transmitted to the communicating party. By contrast with this, if errors occur, CRC check section 14 does not output received data and forms a NACK signal as an ACK/NACK signal to be transmitted to the communicating party.
This will be described more generally.
Assume that the input data sequence of n bits is A=[a0a1 . . . an−2an−1]. a0 is the MSB (Most Significant Bit), that is, the bit to be transmitted first. Assuming that a0, . . . , and an−1 are used as elements of GF(2) (that is, adopt a value of 0 or 1), and the bit sequence is represented by a polynomial equation as in following equation 1.
                    (                  Equation          ⁢                                          ⁢          1                )                                                                                                                A                ⁡                                  (                  D                  )                                            =                            ⁢                                                ∑                                      i                    =                    0                                                        n                    -                    1                                                  ⁢                                                      a                    i                                    ⁢                                      D                                          n                      -                      1                      -                      i                                                                                                                                              =                            ⁢                                                                    a                    0                                    ⁢                                      D                                          n                      -                      1                                                                      +                                                      a                    1                                    ⁢                                      D                                          n                      -                      2                                                                      +                …                +                                                      a                                          n                      -                      3                                                        ⁢                                      D                    2                                                  +                                                      a                                          n                      -                      2                                                        ⁢                  D                                +                                  a                                      n                    -                    1                                                                                                          [        1        ]            
Input data sequence A is subjected to CRC coding and becomes B in following equation 2. CRC coding, which is generally used, is carried out by adding the bit sequence of length c to the tail of the input data sequence of n bits. The added c bits are also referred to as “CRC code.”B=[a0a1 . . . ac−2ac−1r0r1 . . . rc−2rc−1]  (Equation 2)
If CRC code is represented by the polynomial equation of following equation 3, B is represented by the polynomial equation of following equation 4.
                    (                  Equation          ⁢                                          ⁢          3                )                                                                                                                R                ⁡                                  (                  D                  )                                            =                            ⁢                                                ∑                                      i                    =                    0                                                        c                    -                    1                                                  ⁢                                                      r                    i                                    ⁢                                      D                                          c                      -                      1                      -                      i                                                                                                                                              =                            ⁢                                                                    r                    0                                    ⁢                                      D                                          c                      -                      1                                                                      +                                                      r                    1                                    ⁢                                      D                                          c                      -                      2                                                                      +                …                +                                                      r                                          c                      -                      2                                                        ⁢                  D                                +                                  r                                      c                    -                    1                                                                                                          [        2        ]                                (                  Equation          ⁢                                          ⁢          4                )                                                                      B          ⁡                      (            D            )                          =                                            A              ⁡                              (                D                )                                      ⁢                          D              c                                +                      R            ⁡                          (              D              )                                                                      
In CRC coding, R(D) is determined for the predetermined polynomial G(D) of the order c determined in advance such that B(D) can be divided by G(D). That is, R (D) is the residue obtained by diving A (D) Dc by G(D).
Above G(D) is referred to as the “generator polynomial” and is represented by following equation 5.
                    (                  Equation          ⁢                                          ⁢          5                )                                                                                                                G                ⁡                                  (                  D                  )                                            =                            ⁢                                                D                  c                                +                                                      ∑                                          i                      =                      0                                                              c                      -                      1                                                        ⁢                                                            g                      i                                        ⁢                                          D                                              c                        -                        1                        -                        i                                                                                                                                                                    =                            ⁢                                                D                  c                                +                                                      g                    0                                    ⁢                                      D                                          c                      -                      1                                                                      +                                                      g                    1                                    ⁢                                      D                                          c                      -                      2                                                                      +                …                +                                                      g                                          c                      -                      3                                                        ⁢                                      D                    2                                                  +                                                      g                                          c                      -                      2                                                        ⁢                  D                                +                                  g                                      c                    -                    1                                                                                                          [        3        ]            
There may be a case below where the order c of the generator polynomial is referred to as “the order of CRC code.”
To sum up the above, following equation 6 holds. Q (D) is the quotient obtained by dividing A (D) Dc by G(D).B(D)=A(D)Dc+R(D)=G(D)Q(D)  (Equation 6)
n+c bits subjected to CRC coding as described above are transmitted through channel 13. Bit error E (D) (i.e. noise) is added in channel 13.
CRC check is carried out by checking whether or not received value B′ (D)=B (D)+E (D) can be divided by G(D). When there is no bit error with the received value (that is, when E (D)=0), B′ (D) can be divided by G(D). When there is a bit error with the received value, if E (D) cannot be divided by G(D), B′ (D) cannot be divided G(D). Consequently, it is possible to detect whether a bit error has occurred in the channel. If E(D) can be divided by G(D), it is not possible to detect whether or not there is an error by CRC code. However, if the length of c is sufficient, the probability of occurrence of a case where E(D) can be divided by G(D) is low. The values, such as 32 to 8, are usually used for c.
FIG. 2 illustrates how CRC code applied to a more practical system is used.
In FIG. 2, input data A (D) from information source 21 is subjected to CRC coding in CRC coding section 22, and data B(D) subjected to CRC coding is transmitted as transmission data C(D) from error correction coding section 23 to the receiving end through channel 24. The transmitting end carries out CRC coding and then error correction coding. For example, Reed Solomon code, convolution code and turbo code are used for the method of error correction coding.
There is a case where bit error E (i.e. noise) is added in channel 24. The receiving end receives transmission data sequence C′(D) to which bit error E is added, outputs transmission data B′(D) by carrying out error correction decoding in error correction decoding section 25, carries out a CRC check in CRC check section 26 and gives received data A′ based on the CRC check to outputting end 27 (i.e. sink). The receiving end decodes error correction code. By this means, most of the bit errors added in channel 24 are removed. In CRC check in CRC check section 26, whether or not there are errors that cannot be removed by error correction decoding, is checked.